// 最好情况: O(nlog(n)), 最坏情况：O(nlog(n))
export default function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);
  const newLeftArr = mergeSort(leftArr);
  const newRightArr = mergeSort(rightArr);

  // 合并
  let i = 0;
  let j = 0;
  const newArr = [];
  while (i < newLeftArr.length && j < newRightArr.length) {
    if (newLeftArr[i] <= newRightArr[j]) {
      // 修正：比较 left 和 right
      newArr.push(newLeftArr[i]);
      i++;
    } else {
      newArr.push(newRightArr[j]); // 修正：使用 j 索引
      j++;
    }
  }

  // 是否某个数组还有剩余元素
  if (i < newLeftArr.length) {
    newArr.push(...newLeftArr.slice(i));
  }

  if (j < newRightArr.length) {
    newArr.push(...newRightArr.slice(j));
  }

  return newArr;
}

console.log(mergeSort([12, 232, 43, 12, 423, 1, 2, 3]));
